/**
 * 项目名称: Topic_147.cpp
 * 项目路径: study/DataStructure/LinkedList/LeetCode/链表/中等
 * 编辑时间: 2024年07月08日14时42分22秒
 * 用   户: 轻尘
 */

#include <bits/stdc++.h>

using namespace std;

struct ListNode {
    int val;
    ListNode *next;

    ListNode() : val(0), next(nullptr) {}

    ListNode(int x) : val(x), next(nullptr) {}

    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        if(!head->next)return head;

        ListNode * dumm = new ListNode;
        dumm->next = head;
        ListNode * lastSorted = head;
        ListNode * curr = head->next;

        while (curr){
            if(lastSorted->val <= curr->val)lastSorted=lastSorted->next;
            else{
                ListNode * prev = dumm;
                while (prev->next->val <= curr->val)prev = prev->next;
                lastSorted->next = curr->next;
                curr->next = prev->next;
                prev->next = curr;
            }
            curr = lastSorted->next;
        }
        return dumm->next;
    }
};

int main() {

    return 0;
}
